#define _CRT_SECURE_NO_WARNINGS

//#include <stdio.h>
//#include <assert.h>
//#include <stdlib.h>
//#include <stdbool.h>

#include "ALL.h"

typedef int BTDataType;
typedef struct TreeNode
{
	BTDataType data;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(BTDataType x)
{
	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
	assert(newnode);

	newnode->data = x;
	newnode->left = NULL;
	newnode->right = NULL;

	return newnode;
}

TreeNode* BuyTree()
{
	TreeNode* n1 = BuyTreeNode(1);
	TreeNode* n2 = BuyTreeNode(2);
	TreeNode* n3 = BuyTreeNode(3);
	TreeNode* n4 = BuyTreeNode(4);
	TreeNode* n5 = BuyTreeNode(5);
	TreeNode* n6 = BuyTreeNode(6);

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;

	return n1;
}

void PreOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

void InOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

void PostOrder(TreeNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

int TreeNodeSize(TreeNode* root)
{
	return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}

int TreeLeafSize(TreeNode* root)
{
	if (root == NULL) return 0;

	if (root->left == NULL && root->right == NULL) return 1;

	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeHeight(TreeNode* root)
{
	if (root == NULL) return 0;

	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);

	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int TKLevelNodeSize(TreeNode* root, int k)
{
	if (root == NULL) return 0;

	if (k == 1) return 1;

	return TKLevelNodeSize(root->left, k - 1) + TKLevelNodeSize(root->right, k - 1);
}

TreeNode* TreeDataFind(TreeNode* root, BTDataType x)
{
	if (root == NULL) return NULL;

	if (root->data == x) return root;

	TreeNode* lret = TreeDataFind(root->left, x);
	if (lret) return lret;

	TreeNode* rret = TreeDataFind(root->right, x);
	if (rret) return rret;

	return NULL;
}

void LevelOrder(TreeNode* root)
{
	Que q;
	QInit(&q);

	if (root) QPush(&q, root);

	while (!QEmpty(&q))
	{
		TreeNode* front = QFront(&q);
		QPop(&q);
		printf("%d ", front->data);

		if (front->left) QPush(&q, front->left);
		if (front->right) QPush(&q, front->right);
	}

	printf("\n");
	QDestroy(&q);
}

bool TreeComplate(TreeNode* root)
{
	Que q;
	QInit(&q);

	if (root) QPush(&q, root);

	while (!QEmpty(&q))
	{
		TreeNode* front = QFront(&q);
		QPop(&q);

		if (front == NULL) break;

		QPush(&q, front->left);
		QPush(&q, front->right);
	}

	while (!QEmpty(&q))
	{
		TreeNode* front = QFront(&q);
		QPop(&q);

		if (front)
		{
			QDestroy(&q);
			return false;
		}
	}

	QDestroy(&q);
	return true;
}

void TreeDestroy(TreeNode* root)
{
	if (root == NULL) return;

	TreeDestroy(root->left);
	TreeDestroy(root->right);
	free(root);
}

void testInsertSort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	InsertSort(arr, n);
	PrintArray(arr, n);
}

void testSherSort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	SherSort(arr, n);
	PrintArray(arr, n);
}

void testSelectSort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	SelectSort(arr, n);
	PrintArray(arr, n);
}

void testHeapSort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	HeapSort(arr, n);
	PrintArray(arr, n);
}

void testBubbleSort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, n);
	PrintArray(arr, n);
}

void testQuickSort()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, n - 1);
	PrintArray(arr, n);
}

int main()
{
	TreeNode* root = BuyTree();

	PreOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");

	printf("TreeNodeSize = %d\n", TreeNodeSize(root));
	printf("TreeLeafSize = %d\n", TreeLeafSize(root));
	printf("TreeHeight = %d\n", TreeHeight(root));
	printf("TreeKNodeSize = %d\n", TKLevelNodeSize(root, 3));

	printf("TreeFindData = %d\n", TreeDataFind(root, 6)->data);

	LevelOrder(root);

	if (TreeComplate(root)) printf("Full binary tree!\n");
	else printf("Not full binary tree!\n");

	TreeDestroy(root);


	testInsertSort();
	testSherSort();
	testSelectSort();
	testHeapSort();
	testBubbleSort();
	testQuickSort();


	return 0;
}